package ustc.xiaoyang.karl.linkedlist;

/**
 * 面试题02.07 链表相交
 */
public class InterSectionOfLinkedList_02_07 {
    public static void main(String[] args) {

    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        int sizeA = 0, sizeB = 0;
        while(p != null){
            sizeA++;
            p = p.next;
        }
        while(q != null){
            sizeB++;
            q = q.next;
        }
        int diff = Math.abs(sizeA - sizeB);
        p = sizeA > sizeB ? headA : headB;
        q = sizeA > sizeB ? headB : headA;
        for(int i = 0; i < diff; i++){
            p = p.next;
        }
        while(p != null){
            if(p == q){
                return p;
            }
            p = p.next;
            q = q.next;
        }
        return null;

    }
}
